package 二叉树;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 左叶子之和
 * 计算给定二叉树的所有左叶子之和
 * User: zhaixiaolong Date:2024/2/28 9:13 ProjectName: algorithm Version:
 */
public class LeftLeavesSum {


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        int leftLeavesSum = sumLeftLeaves(treeNode);
        System.out.println(leftLeavesSum);
    }

    /**
     * 左叶子之和
     *
     * @param treeNode
     * @return
     */
    public static int sumLeftLeaves(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        TreeNode leftNode = treeNode.getLeft();
        TreeNode rightNode = treeNode.getRight();
        if (leftNode != null && leftNode.getLeft() == null && leftNode.getRight() == null) {
            return leftNode.val + sumLeftLeaves(rightNode);
        }
        return sumLeftLeaves(leftNode) + sumLeftLeaves(rightNode);
    }

    /**
     * 找树左下角的值
     * 给定一个二叉树，在树的最后一行找到最左边的值
     *
     * @return
     */
    public static int getTreeLeft(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int leftVal = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    leftVal = node.val;
                }
                if (node.getLeft() != null) {
                    queue.add(node.left);
                }
                if (node.getRight() != null) {
                    queue.add(node.right);
                }
            }
        }
        return leftVal;
    }


}
